package net.jedi.cfire;

import java.util.ArrayList;
import java.util.List;

import jsr166y.forkjoin.ForkJoinPool;
import jsr166y.forkjoin.RecursiveAction;

public class CFire extends RecursiveAction {
	final int depth;
	final int[] twists;
	final int[][] puzzle;
	
	private static final int[] kink_index = {2,3,4,6,7,9,10,11,13,15,16,17,18,20,22,24};
	private static final int[] kink_map = {0,0,1,1,1,0,1,1,0,1,1,1,0,1,0,1,1,1,1,0,1,0,1,0,1,0,0};
	private static final int[][] units = {		/* The unit vectors. */
		{1,0,0},  /* 0 */
		{0,1,0},  /* 1 */
		{0,0,1},  /* 2 */
		{-1,0,0}, /* 3 */
		{0,-1,0}, /* 4 */
		{0,0,-1}  /* 5 */
	};
	private static final int[][] rotations = {	/* Rotations of the unit vectors. */
		{2,1,5,4},
		{0,2,3,5},
		{1,0,4,3},
		{5,4,2,1},
		{3,5,0,2},
		{4,3,1,0}
	};
	
	CFire( int depth, int[] twists, int[][] puzzle) {
		this.depth = depth;
		this.twists = twists;
		this.puzzle = puzzle;
	}

	/**
	 * Tries all the possible rotations at the given depth and below and prints message if solution found.
	 */
	@Override
	protected void compute() {
		rotate(depth, twists, puzzle);
	}
	
	private void rotate(final int d, final int[] t, final int[][] p) {
		if(d == t.length)
			return;
		if(d == 5) System.out.print("5 ");	// FOR DEBUGGING ONLY
		if(d < 3) {
			// concurrent
			List<CFire> actions = new ArrayList<CFire>();
			for (int spin=0; spin < 4; spin++) {
				int[] tprime = t.clone();
				tprime[d] = spin;
				final int[][] pprime = project(d, tprime, p);
				actions.add(new CFire(d+1, tprime, pprime));
			}
			forkJoin(actions);
		} else {
			// sequential
			for (int spin=0; spin < 4; spin++) {
				int[] tprime = t.clone();
				tprime[d] = spin;
				final int[][] pprime = project(d, tprime, p);
				rotate(d+1, tprime, pprime);
			}
		}
	}

	/**
	 * Projects the given twists onto the puzzle and prints message if solution found.
	 * @return clone of p
	 */
	private int[][] project(final int depth, final int[] t, final int[][] p) {
		int ret[][] = p.clone();
		int d=0, orientation=0;
		for(int i=0; i<p.length-1; i++) {
			if(kink_map[i]==1) {
				orientation = rotations[orientation][t[d++]];
			}
			ret[i+1][0] = ret[i][0] + units[orientation][0];	// X
			ret[i+1][1] = ret[i][1] + units[orientation][1];	// Y
			ret[i+1][2] = ret[i][2] + units[orientation][2];	// Z
			
			// TODO  Add optional optimization here: return if i<starting, and filter spurious sol'ns later
			
			// test for proximity
			if( Math.abs(ret[i+1][0] - 1) > 1
				|| Math.abs(ret[i+1][1] - 1) > 1
				|| Math.abs(ret[i+1][2] - 1) > 1 ) {
				return ret;
			}
			
			// test for collision
			if( i > 2 && hasCollision(i-1, i+1, ret)) {
				return ret;
			}
		}
		
		for(int j=0; j<t.length; j++) System.out.print(t[j] + " "); System.out.println("!");
		printPuzzle(ret);
		
		return ret;
	}

	private void printPuzzle(final int[][] p) {
		System.out.print("{ ");
		for(int i=0; i<p.length; i++) {
			printPoint(p[i]);
			if(i<p.length-1) System.out.print(", ");
		}
		System.out.println(" }, ");
	}

	private void printPoint(int[] point) {
		StringBuilder s = new StringBuilder("{");
		s.append(point[0]).append(',').append(point[1]).append(',').append(point[2]).append('}');
		System.out.print(s.toString());
	}

	private boolean hasCollision(int startFrom, final int compareTo, final int[][] p) {
		for( ; startFrom>=0; startFrom-- ) {
			if( p[compareTo][0] == p[startFrom][0] 
			    && p[compareTo][1] == p[startFrom][1]
			    && p[compareTo][2] == p[startFrom][2] ) {
				return true;
			}
		}
		return false;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		final int[] t = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
		final int[][] p = {
				{0,0,0},{0,0,0},{0,0,0},
				{0,0,0},{0,0,0},{0,0,0},
				{0,0,0},{0,0,0},{0,0,0},
				{0,0,0},{0,0,0},{0,0,0},
				{0,0,0},{0,0,0},{0,0,0},
				{0,0,0},{0,0,0},{0,0,0},
				{0,0,0},{0,0,0},{0,0,0},
				{0,0,0},{0,0,0},{0,0,0},
				{0,0,0},{0,0,0},{0,0,0}
				};
		
		ForkJoinPool pool = new ForkJoinPool();
		pool.invoke(new CFire(0, t, p));	
	}

}
